1. Definition
An instance of the data type partition consists of a finite set of
items (predefined type
partition) and a partition of this set
into blocks.
2. Creation
P
Creates an instance P of type partition and initializes it to the empty partition.
2. Operations
& truecm & truecm &
partition_item make_block
returns a new
partition it and adds
the block {it} to partition P.
3. Implementation
Partitions are implemented by the union find algorithm with weighted union and path compression (cf. [T83]). Any sequence of n make_block and m≥n other operations takes time O(mα(m, n)).
4. Example
Spanning Tree Algorithms (cf. graph)